package oj_leetcode;

import java.util.Stack;

public class TrappingRainWater {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] == 0) {
                continue;
            }
            boolean flag = true;
            int used = 0;
            while (flag && !stack.isEmpty()) {
                if (height[i] < height[stack.peek()]) {
                    flag = false;
                    res += (i - stack.peek() - 1) * (height[i] - used);
                } else {
                    int index = stack.pop();
                    res += (i - index - 1) * (height[index] - used);
                    used = height[index];
                }
            }
            stack.push(i);
        }
        return res;
    }
}
